/*
 * @Author       : wangzeyu 2309335887@qq.com
 * @Date         : 2023-06-25 15:58:38
 * @LastEditors  : WangZeYu
 * @LastEditTime : 2023-06-29 18:39:32
 * @FilePath     : \algorithm\insertSort.js
 * @Description  : 插入排序
 */
function insertSort(arr) {
  let _handle = []
  _handle.push(arr[0])
  for (let i = 1; i < arr.length; i++) {
    let _A = arr[i]
    for (let j = _handle.length - 1; j >= 0; j--) {
      let _B = _handle[j]
      if (_A > _B) {
        _handle.splice(j + 1, 0, _A)
        break
      }
      if (j === 0) {
        _handle.unshift(_A)
      }
    }
  }
  return _handle
}
module.exports = {insertSort}
let a = [3, 3, 5, 6, 9, 9, 15, 15, 3, 3, 8]
console.log(insertSort(a))